package string

func Partition(s string) [][]string {
	var res [][]string
	var backtrack func(s string, start, end int, isPal [][]bool)
	var track []string

	{
		backtrack = func(s string, start, end int, isPal [][]bool) {
			if start > end {
				tmp := make([]string, len(track))
				copy(tmp, track)
				res = append(res, tmp)
			}

			for ll := 1; ll <= end-start+1; ll++ {
				if !isPal[start][start+ll-1] {
					continue
				}

				track = append(track, s[start:start+ll])
				backtrack(s, start+ll, end, isPal)
				track = track[:len(track)-1]
			}
		}
	}

	isPal := make([][]bool, len(s))
	for i := range isPal {
		isPal[i] = make([]bool, len(s))
		isPal[i][i] = true
	}

	for j := 1; j < len(s); j++ {
		for i := 0; i < j; i++ {
			if j-i < 3 {
				isPal[i][j] = (s[i] == s[j])
			} else {
				isPal[i][j] = (s[i] == s[j]) && isPal[i+1][j-1]
			}
		}
	}

	backtrack(s, 0, len(s)-1, isPal)

	return res
}
